package com.example.leetcode.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree implements AbstractBinaryTree {

    private NodeTree root = new NodeTree();

    public NodeTree getRoot() {
        return root;
    }

    public void printNode(NodeTree NodeTree) {

        if (NodeTree.data == null) {
            System.out.print("");
        } else {
            System.out.print(NodeTree.data);
        }
    }

    public BinaryTree(String tree) {
        String[] treeNodes = tree.split(",");
        createTreeByRecursion(treeNodes);
    }

    private int createTreeByRecursion(NodeTree NodeTree, String[] treeNodes, int n) {

        if ("#".equals(treeNodes[n]))
            return n + 1;

        NodeTree.data = treeNodes[n];

        NodeTree.left = new NodeTree();
        int left = createTreeByRecursion(NodeTree.left, treeNodes, n + 1);

        NodeTree.right = new NodeTree();
        int right = createTreeByRecursion(NodeTree.right, treeNodes, left);

        return right;
    }

    public void createTreeByRecursion(String[] treeNodes) {
        createTreeByRecursion(root, treeNodes, 0);
    }

    /**
     * 先序非递归创建
     */

    public void createTree(String[] treeNodes) {

        Stack<NodeTree> stack = new Stack<>();

        int index = 0;

        NodeTree NodeTree = root;

        while (index < treeNodes.length) {

            while (true) {

                if ("#".equals(treeNodes[index])) {

                    NodeTree = stack.pop();

                    if (NodeTree.flag == false) {
                        NodeTree.left = null;
                        NodeTree.flag = true;
                        stack.push(NodeTree);
                    } else {
                        NodeTree.right = null;
                    }

                    // 记得加1
                    index++;
                    break;
                }

                if (NodeTree.flag == true) {
                    NodeTree.right = new NodeTree();
                    NodeTree = NodeTree.right;
                }

                NodeTree.data = treeNodes[index];
                stack.push(NodeTree);
                NodeTree.left = new NodeTree();
                NodeTree = NodeTree.left;
                index++;
            }

            if (NodeTree.flag == false) {
                stack.push(NodeTree);
                NodeTree.flag = true;
                NodeTree = NodeTree.right;
            } else {
                NodeTree = stack.peek();
                NodeTree.flag = true;
            }

        }

    }

    // 递归调用的方法,需要将root传递进去
    private void printPreOderByRecursion(NodeTree NodeTree) {

        if (NodeTree == null)
            return;

        printNode(NodeTree);
        printPreOderByRecursion(NodeTree.left);
        printPreOderByRecursion(NodeTree.right);

    }
    @Override
    public void printPreOderByRecursion() {

        printPreOderByRecursion(root);
    }

    private void printInOderByRecursion(NodeTree NodeTree) {

        if (NodeTree == null)
            return;

        printInOderByRecursion(NodeTree.left);
        printNode(NodeTree);
        printInOderByRecursion(NodeTree.right);

    }
    @Override
    public void printInOderByRecursion() {
        printInOderByRecursion(root);
    }
    private void printPostOderByRecursion(NodeTree NodeTree) {

        if (NodeTree == null)
            return;

        printPostOderByRecursion(NodeTree.left);
        printPostOderByRecursion(NodeTree.right);
        printNode(NodeTree);

    }
    @Override
    public void printPostOderByRecursion() {

        printPostOderByRecursion(root);
    }

    // 非递归遍历二叉树

    // 先序遍历
    @Override
    public void printPreOder() {

        Stack<NodeTree> stack = new Stack<>();

        NodeTree tempNode = root;

        while (true) {

            while (tempNode != null) {
                printNode(tempNode);
                stack.push(tempNode);
                tempNode = tempNode.left;
            }

            if (stack.isEmpty()) {
                break;
            }

            tempNode = stack.pop();
            tempNode = tempNode.right;

        }

    }

    // 中序遍历
    @Override
    public void printInOder() {

        Stack<NodeTree> stack = new Stack<>();

        NodeTree tempNode = root;

        while (true) {

            while (tempNode != null) {
                stack.push(tempNode);
                tempNode = tempNode.left;
            }

            if (stack.isEmpty()) {
                break;
            }
            tempNode = stack.pop();
            printNode(tempNode);
            tempNode = tempNode.right;

        }

    }

    // 后序遍历
    @Override
    public void printPostOder() {

        Stack<NodeTree> stack = new Stack<>();

        NodeTree tempNode = root;

        while (true) {

            while (tempNode != null) {
                if (tempNode.flag == true) {
                    tempNode = tempNode.right;
                } else {
                    stack.push(tempNode);
                    tempNode = tempNode.left;
                }

            }

            tempNode = stack.pop();

            if (tempNode.flag == false) {
                stack.push(tempNode);
                tempNode.flag = true;
                tempNode = tempNode.right;
            } else {
                printNode(tempNode);
                if (stack.isEmpty()) {
                    break;
                }
                tempNode = stack.peek();
                tempNode.flag = true;
            }

        }

    }

    // 层序遍历 利用队列
    @Override
    public void printLevelOrder() {

        Queue<NodeTree> queue = new LinkedList<>();

        NodeTree tempNode = root;

        queue.offer(tempNode);

        while (!queue.isEmpty()) {

            NodeTree topNode = queue.poll();

            if (topNode == null)
                continue;

            printNode(topNode);
            queue.offer(topNode.left);
            queue.offer(topNode.right);

        }

    }

    // 树高 递归，分别求出左子树的深度、右子树的深度，两个深度的较大值+1
    public int getHeightByRecursion(NodeTree NodeTree) {

        if (NodeTree == null) {
            return 0;
        }
        int left = getHeightByRecursion(NodeTree.left);
        int right = getHeightByRecursion(NodeTree.right);
        return 1 + Math.max(left, right);

    }

    /**
     * 为什么不直接写成调用 root,而是另写一个方法去调用呢 因为,这样可以不再为root,单独设置一个临时变量去存贮
     * 而且也固定外部调用的方法,而不用关心内部的实现
     */
    @Override
    public void printHeight() {

        int height = getHeightByRecursion(root);

        System.out.print(height);
    }

    // 利用层序遍历,得到树的最大宽度
    @Override
    public void printMaxWidth() {

        Queue<NodeTree> queue = new LinkedList<>();
        Queue<NodeTree> queueTemp = new LinkedList<>();

        int maxWidth = 1;

        NodeTree tempNode = root;

        queue.offer(tempNode);

        while (!queue.isEmpty()) {

            while (!queue.isEmpty()) {

                NodeTree topNode = queue.poll();

                if (topNode == null)
                    continue;

                if (topNode.left.data != null) {

                    queueTemp.offer(topNode.left);
                }

                if (topNode.right.data != null) {

                    queueTemp.offer(topNode.right);
                }

            }

            maxWidth = Math.max(maxWidth, queueTemp.size());
            queue = queueTemp;
            queueTemp = new LinkedList<>();
        }

        System.out.print(maxWidth);
    }
}
